#include "Heap.h"

void Swap(int* buf1, int* buf2)
{
	int temp = *buf1;
	*buf1 = *buf2;
	*buf2 = temp;
}
void Heapinit(heap* heap)
{
	heap->arr = NULL;
	heap->size = 0;
	heap->capcity = 4;
}
void HeapPush(heap* heap,int x)
{
	if (heap->arr == NULL)
	{
		int* temp = (int*)malloc(sizeof(int) * 10);
		if(temp != NULL)
		{
			heap->arr = temp;
			heap->arr[heap->size++] = x;
			heap->capcity = 10;
		}
	}
	else
	{
		if (heap->size == heap->capcity)
		{
			int* temp = (int*)realloc(heap->arr, sizeof(int) * (heap->capcity * 2));
			if (temp != NULL)
			{
				heap->arr = temp;
				heap->capcity *= 2;
			}
			heap->arr[heap->size++] = x;
		}
		else
		{
			heap->arr[heap->size++] = x;
		}
	}

	AdjustUp(heap->arr, heap->size - 1);
}
void AdjustUp(int* arr,unsigned int child)
{
	unsigned int parent = (child-1)/2;
	while (child > 0)
	{
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void AdjustDown(int* a, int length, int parent)
{
	int child = parent * 2 + 1;
	while (child < length)
	{
		if (child + 1 < length && a[child] > a[child + 1])
		{
			child++;
		}
		if (a[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapPrint(heap* heap)
{
	assert(heap->arr);
	assert(heap->size);
	for (int i = 0; i < heap->size; i++)
	{
		printf("%d ", heap->arr[i]);
	}
	printf("\n");
}
void HeapPop(heap* heap)
{
	assert(heap);
	assert(heap->arr);
	assert(heap->size > 0);
	Swap(&heap->arr[0], &heap->arr[heap->size - 1]);
	heap->size--;
	AdjustDown(heap->arr, heap->size, 0);
}
void HeapDesroty(heap* heap)
{
	assert(heap->arr);

	free(heap->arr);
	heap->capcity = heap->size = 0;
}
int HeapTop(heap* heap)
{
	assert(heap->arr);
	assert(heap->size > 0);

	return heap->arr[0];
}
int HeapSize(heap* heap)
{
	assert(heap->arr);
	
	return heap->size;
}
void HeapCreat(heap* heap, int* array, int length)
{
	if (heap->arr == NULL)
	{
		int* temp = (int*)realloc(heap->arr, sizeof(int) * length);
		if (temp != NULL)
		{
			heap->arr = temp;
			heap->size = length;
		}
		heap->capcity = length;
	}
	memcpy(heap->arr, array, sizeof(int) * length);
	for (int i = (length - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(heap->arr, length, i);
	}
}
void HeapSort(int* arr, int length)
{
	assert(arr);
	for (int i = (length - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, length, i);
	}
	
	int end = length - 1;
	while (end)
	{
		Swap(&arr[0],&arr[end]);
		AdjustDown(arr, end, 0);
		end--;
	}
}
void PrintfTopk(int* a, int n, int k)
{
	srand(time(0));
	int* arr = (int*)malloc(sizeof(int) * k);
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, k, i);
	}

	for (int i = k; i < n; i++)
	{
		if (a[i] > a[0])
		{
			a[0] = a[i];
		}
		AdjustDown(a, k, 0);
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", a[i]);
	}
}
void Test01()
{
	int array[] = { 27,15,19,18,28,34,65,49,25,37 };
	heap p;
}
void Test02()
{
	int array[] = { 27,15,19,18,28,34,65,49,25,37 };
	heap p;
	PrintfTopk(array, 10, 5);
}
int main()
{
	Test02();
	return 0;
}